#pragma once

#include <ClanLib/core.h>

struct ConvexHullPoint;

/*
 * data structure for saving convex hull lines
 * this are just sets of two convex hull points each and can represent a tangent, for example
 * always make sure that the left and right points of these lines are really left / right in respect of the other
 * (to be left means having lower x coordinate) - else, methods these lines get passed to will behave unexpectedly
 */
class ConvexHullLine
{
public:
	ConvexHullLine(ConvexHullPoint* leftPoint, ConvexHullPoint* rightPoint)
		: left(leftPoint),
		right(rightPoint)
	{
	}
	ConvexHullPoint* left;
	ConvexHullPoint* right;
};

/*
 * data structures for holding convex hull points
 * if correctly wired up, each convex hull points is linked to all other points of its convex hull
 * these can be accessed by iterating through the neighbors in clockwise or counterclockwise order
 */
struct ConvexHullPoint
{
	inline ConvexHullPoint(const clan::Vec2d point);
	/*
	 * returns true if convex hull point lies below given line not - false, if it is part of, on, or above given line.
	 */
	inline bool IsBelowLine(const ConvexHullPoint* leftLineEnd, const ConvexHullPoint* rightLineEnd) const;
	inline bool IsBelowLine(const ConvexHullLine& convexHullLine) const;
	/*
	 * deletes convex hull point neighbors clockwise until clockwise end is encountered. This and clockwise end itself won't get deleted.
	 */
	inline void DeleteClockWiseUntil(const ConvexHullPoint* clockwiseEnd) const;
	
	const clan::Vec2d location;
	ConvexHullPoint* nextPointClockwise;
	ConvexHullPoint* nextPointCounterClockwise;
};

inline ConvexHullPoint::ConvexHullPoint( clan::Vec2d point )
	: location(point)
{

}

inline bool ConvexHullPoint::IsBelowLine(const ConvexHullPoint* leftLineEnd, const ConvexHullPoint* rightLineEnd) const
{
	return location.y <
		leftLineEnd->location.y +
		(location.x - leftLineEnd->location.x)
		/ (rightLineEnd->location.x - leftLineEnd->location.x)
		* (rightLineEnd->location.y - leftLineEnd->location.y);
}

inline bool ConvexHullPoint::IsBelowLine(const ConvexHullLine& convexHullLine) const
{
	return IsBelowLine(convexHullLine.left, convexHullLine.right);
}

void ConvexHullPoint::DeleteClockWiseUntil( const ConvexHullPoint* clockwiseEnd ) const
{
	const ConvexHullPoint *actual, *next;
	actual = this->nextPointClockwise;
	next = actual->nextPointClockwise;
	while (actual != clockwiseEnd)
	{
		delete actual;
		actual = next;
		next = actual->nextPointClockwise;
	}
}
